/**
 * 337. 打家劫舍 III
 * https://leetcode-cn.com/problems/house-robber-iii/
 */
const { createTreeNode } = require('../../libs/public');

let memory;

/**
 * @param {TreeNode} root
 * @param {boolean} freeze
 * @return {number}
 */
function robAtNode(root, freeze = false) {
  if (!root) {
    return 0;
  }
  let cache = memory.get(root);
  if (!cache) {
    cache = [-1, -1];
    memory.set(root, cache);
  }
  if (cache[0] < 0) {
    cache[0] = robAtNode(root.left) + robAtNode(root.right);
  }
  if (freeze) {
    return cache[0];
  }
  if (cache[1] < 0) {
    cache[1] = robAtNode(root.left, true) + robAtNode(root.right, true) + root.val;
  }
  return Math.max(cache[0], cache[1]);
}

/**
 * @param {TreeNode} root
 * @return {number}
 */
function rob(root) {
  memory = new Map();
  return robAtNode(root);
}

console.log(rob(createTreeNode([3, 2, 3, null, 3, null, 1])) === 7);
console.log(rob(createTreeNode([3, 4, 5, 1, 3, null, 1])) === 9);
console.log(rob(createTreeNode([4, 2, null, 1, 3])) === 8);
